package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

/**
 * 面试题 04.06. 后继者
 * 剑指 Offer II 053. 二叉搜索树中的中序后继
 *
 * @Author liw
 * @Date 2021/5/20 16:17
 * @Version 1.0
 */
public class InorderSuccessor {

    boolean flag = false;
    TreeNode node = null;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        find(root, p);
        return node;
    }
    public boolean find(TreeNode root, TreeNode p) {
        if (root == null) {
            return false;
        }
        if (find(root.left, p)) {
            return true;
        }
        if (flag) {
            node = root;
            return true;
        }
        if (root.val == p.val) {
            flag = true;
        }
        return find(root.right, p);
    }

    private TreeNode p;
    private TreeNode t;
    private int f = 0;
    public TreeNode inorderSuccessor2(TreeNode root, TreeNode p) {
        this.p = p;
        find(root);
        return t;
    }

    private void find (TreeNode node) {
        if (node == null) {
            return;
        }
        find(node.left);
        if (f == 1) {
            t = node;
            f = 2;
            return;
        }
        if (node.val == p.val) {
            f = 1;
        }
        find(node.right);
    }
}
